package Study1;

public class Study10 {
/*
删除链表中重复的结点
在一个排序的链表中，存在重复的结点，
请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。
 例如，链表 1->2->3->3->4->4->5  处理后为 1->2->5
* */
/*import java.util.*;
    *//*
     public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }
    *//*
    public class Solution {
        public ListNode deleteDuplication(ListNode pHead) {
            ListNode newHead = new ListNode(-1);
            ListNode cur = pHead;
            ListNode tmp = newHead;
            if (null == pHead) {  // 空链表，返回null
                return null;
            }

            while (null != cur) { // 遍历链表
                if (null != cur.next && cur.val == cur.next.val) { // 不为空，防止空引用，并判断相邻是否相等
                    while (null != cur.next && cur.val == cur.next.val) { // 同理
                        cur = cur.next; // 相同，移动跳过相同的节点
                        //     cur = cur.next.next; 不可以这样写，防止非法空的，越界访问，以及空引用
                    }
                    cur = cur.next; // 跳出循环再，移动一次节点
                } else { // 把不是重复的节点尾插法，插入
                    tmp.next = cur;
                    tmp = tmp.next;
                    cur = cur.next;
                }
            }
            tmp.next = null; // 最后一个，尾节点置为 null
            return newHead.next; // 返回第二个节点的地址，因为第二个节点才存放着，该链表中的数值

        }
    }*/



    /*
     链表分割
     现有一链表的头指针 ListNode* pHead，给一定值x，
     编写一段代码将所有小于x的结点排在其余结点之前，
     且不能改变原来的数据顺序，返回重新排列后的链表的头指针
    * */
   /* import java.util.*;

    *//*
    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }*//*
    public class Partition {
        public ListNode partition(ListNode pHead, int x) {
            // write code here
            ListNode as = null;
            ListNode ae = null;
            ListNode bs = null;
            ListNode be = null;


            while (null != pHead) { // 遍历整个链表
                if (pHead.val < x) { // 存放小于 x 的数值的节点
                    if (null == ae) { // 第一次插入
                        as = pHead;
                        ae = pHead;
                    } else {
                        as.next = pHead;
                        as = as.next;
                    }

                } else {
                    // 存放大于 x 的数值的节点
                    if ( null == be) {  // 第一次插入
                        bs = pHead;
                        be = pHead;
                    } else {
                        bs.next = pHead;
                        bs = bs.next;
                    }

                }
                pHead = pHead.next;  // 移动节点
            }
            if (null == ae) { // ae 链表一个都没有插入 则全部插入到了 be 中了
                return be;
            }
            if (null == be) { // be 链表中一个都没有插入 则全部插入到了 ae 中去了
                return ae;
            }
            as.next = be;  // 拼接
            bs.next = null; // 最后的尾节点置为 null
            return ae;

        }
    }

*/



/*链表中倒数第k个结点
* 输入一个链表，输出该链表中倒数第k个结点。
* import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
/*public class Solution {
    public ListNode FindKthToTail(ListNode head, int k) {
        ListNode falst = head;
        ListNode slow = head;

        if (head == null) {
            return null;
        }
        // 判断 k的合理性
        if (k < 0) {
            return null;
        }

        while (k > 0) {
            if (null == falst) {
                return null;
                // 如果 false 都为 null了，k 还没有减到低，说明 k 太大了不合理
            }
            k--;
            falst = falst.next;
        }

        // 一起走，当 falst null 等于 0
        while (null != falst ) {
            falst = falst.next;
            slow = slow.next;
        }
        return slow;
    }
}*/






/*
面试题：链表的中间节点
给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点
遍历一次
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 *

 */
    /*
class Solution {
    2倍速，中间1/2
    public ListNode middleNode(ListNode head) {
        ListNode falst = head;
        ListNode slow = head;

        while(null != falst && null != falst.next) {
        // 注意 这里的 循环判断的条件是不可以，调换的，因为防止 falst ==null,
        // 而发生 falst.next 空的引用的错误，以及短路，falst.next.next 会跳过 falst
            falst = falst.next.next;
            slow = slow.next;
        }

        return slow;

    }
}
*/

    /* 面试题：反转单链表
    遍历一次
    * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。*/
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */

    // 方法一
    /*class Solution {
        public ListNode reverseList(ListNode head) {
            ListNode prev = null;
            ListNode cur = head;
            ListNode newHead = null;

            while(null != cur) {
                ListNode nextCur = cur.next;
                if(null == nextCur) {
                    newHead = cur;
                }
                cur.next = prev;
                prev = cur;
                cur = nextCur;
            }
            return newHead ;

        }
    }*/


    // 方法2
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    /*class Solution2 {
        // 利用头插法实现
        public ListNode reverseList(ListNode head) {
            ListNode newhead = new ListNode(0); // 创建一个新链表
            ListNode cur = head;                // 拷贝该链表的头节点
            ListNode curNext = null;            // 拷贝 head.next节点的地址

            if( null == head) {                // 空，直接返回它自身
                return head;
            }

            while(null != cur) {

                curNext = cur.next;               // 拷贝 head.next节点的地址
                cur.next = newhead;
                newhead = cur;
                cur = curNext;                   // 配合拷贝的 head.next节点移动
            }
            head.next = null;

            return newhead;


        }
    }
}*/
}